// https://leetcode.cn/problems/reorder-list/
// Created by ade on 2022/7/27.
// L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    void reorderList(ListNode *head) {
        if (!head || !head->next) return;
        ListNode * mid = middleNode(head);
        ListNode * end = reverseList(mid->next, nullptr);
        mergeList(head, end);
    }

    void mergeList(ListNode *h1, ListNode *h2) {
        while (h2){
            ListNode * h1Next = h1->next;
            ListNode * h2Next = h2->next;
            h1->next = h2;
            h2->next = h1Next;
            h1 = h1Next;
            h2 = h2Next;
        }
        h1->next = nullptr;
    }

    ListNode *middleNode(ListNode *node) {
        ListNode *slow = node;
        ListNode *fast = node->next;
        while (fast->next) {
            slow = slow->next;
            fast = fast->next;
            if (fast->next) {
                fast = fast->next;
            }
        }
        return slow;
    }

    ListNode *reverseList(ListNode *start, ListNode *end) {
        ListNode * prev = nullptr;
        while(start != end){
            ListNode * next = start->next;
            start->next = prev;
            prev = start;
            start = next;
        }
        return prev;
    }

    ListNode *init() {
        ListNode *head1 = new ListNode(1);
        ListNode *head2 = new ListNode(2);
        ListNode *head3 = new ListNode(3);
        ListNode *head4 = new ListNode(4);
        ListNode *head5 = new ListNode(5);
        head1->next = head2;
        head2->next = head3;
        head3->next = head4;
        head4->next = head5;
        return head1;
    }

    void show(ListNode *head) {
        while (head) {
            cout << head->val << ",";
            head = head->next;
        }
        cout << endl;
    }
};

int main() {
    Solution so;
    ListNode *head = so.init();
//    ListNode * mid = so.middleNode(head);
    so.reorderList(head);
//    cout << mid->val << endl;
    so.show(head);
    return 0;

}